The invention relates to a method for an automatic extraction of the structure of a video sequence that corresponds to successive frames, comprising the following steps:
(1) a shot detection step, provided for detecting the boundaries between consecutive shotsxe2x80x94a shot being a set of contiguous frames without editing effectsxe2x80x94and using a similarity criterion based on a computation of the mean displaced frame difference curve and the detection of the highest peaks of said curve;
(2) a partitioning step, provided for splitting each shot into sub-entities, called micro-segments;
(3) a clustering step, provided for creating a final hierarchical structure of the processed video sequence.
The invention also relates to a corresponding method for indexing data, to a device for carrying out said method, and to an image retrieval system in which said method is implemented. The technique of the invention will be particularly well-suited for use in applications that are in relation with the MPEG-7 standard.
The future MPEG-7 standard is intended to specify a standard set of descriptors that can be used to describe various types of multimedia information. The description thus associated with a given content allows fast and efficient searching for material of a user""s interest. The invention relates more specifically to the case of representation of video sequences, intended to provide for users modalities of search information. For a video sequence, the goal of a table of contents description of this document is to define the structure of this sequence in a hierarchical fashion, similarly to what is done for books, in which texts are divided into chapters and paragraphs: the original sequence is subdivided into sub-sequences, which may be further divided into shorter sub-entities.
A method for defining such a structure is described in a european patent application previously filed by the Applicant with the number 99402594.8 (PHF99593). According to said document, the method is divided into three steps, which are, as shown in FIG. 1: a shot detection step 11 (in a sequence of pictures, a video shot is a particular sequence which shows a single background, i.e. a set of contiguous frames without editing effects), a partitioning step 12, for the segmentation of the detected shots into entities exhibiting consistent camera motion characteristics, and a shot clustering step 13.
Concerning the shot detection step, several solutions were already proposed in the document xe2x80x9cA survey on the automatic indexing of video dataxe2x80x9d, R. Brunelli and al., Journal of Visual Communication and Image Representation, volume 10, number 2, June 1999, pp. 58 78-112. In the method described in the cited document, the first step 11 detects the transitions between consecutive shots by means of two main sub-steps: a computation sub-step 111, allowing to determine a mean Displaced Frame Difference (mDFD) curve, and a segmentation sub-step 112.
The mDFD curve computed during the sub-step 111 is obtained taking into account both luminance and chrominance information. With, for a frame at time t, the following definitions:
luminance Y={fk(i, j, t)}k=Yxe2x80x83xe2x80x83(1)
chrominance components (U, V)={fk(i, j, t)}k=U, Vxe2x80x83xe2x80x83(2)
the DFD is given by
DFDK(i,j; txe2x88x921, t+1)=fk(i,j, t+1)xe2x88x92fk(ixe2x88x92dx(i,j), jxe2x88x92dy(i,j), txe2x88x921)xe2x80x83xe2x80x83(3)
and the mDFD by:                               mDFD          ⁡                      (            t            )                          =                              1                                          I                x                            ⁢                              I                y                                              ⁢                                    ∑              k                              Y                ,                U                ,                V                                      ⁢                                          w                k                            ⁢                                                ∑                                      i                    ,                    j                                                                              I                      x                                        ⁢                                          I                      y                                                                      ⁢                                  "LeftBracketingBar"                                                            DFD                      k                                        ⁡                                          (                                              i                        ,                                                  j                          ;                                                      xe2x80x83                                                    ⁢                                                      t                            -                            1                                                                          ,                                                  t                          +                          1                                                                    )                                                        "RightBracketingBar"                                                                                        (        4        )            
where Ix, Iy are the image dimensions and wk the weights for Y, U, V components. An example of the obtained curve (and of the corresponding filtered one), showing ten shots s1 to s10, is illustrated in FIG. 2 with weights that have been for instance set to {wY, wU, wV}={1, 3, 3}. In this example, the highest peaks of the curve correspond to the abrupt transitions from one frame to the following one (frames 21100, 21195, 21633, 21724), while, on the other side, the oscillation from frame 21260 to frame 21279 corresponds to a dissolve (a gradual change from one camera record to another one by simple linear combination of the frames involved in this dissolve process) and the presence of large moving foreground objects in frames 21100-21195 and 21633-21724 creates high level oscillations of the mDFD curve.
The sub-step 112, provided for detecting the video editing effects and segmenting the mDFD curve into shots, uses a threshold-based segmentation to extract the highest peaks of the mDFD curve (or another type of mono-dimensional curve), as described for instance in the document xe2x80x9cHierarchical scene change detection in an MPEG-2 compressed video sequencexe2x80x9d, T. Shin and al, Proceedings of the 1998 IEEE International Symposium on Circuits and Systems, ISCASxe2x80x298, vol.4, March 1998, pp.253-256.
The second step 12 is a temporal segmentation provided for splitting each detected shot into sub-entities presenting a very high level of homogeneity on camera motion parameters. It consists of two sub-steps: an oversegmentation sub-step 121, intended to dividing each shot into so-called micro-segments which must show a very high level of homogeneity, and a merging sub-step 122.
In order to carry out the first sub-step 121, it is necessary to define first what will be called a distance, (the distances thus defined allow to compare the micro-segments), and also a parameter allowing to assess the quality of a micro-segment or a partition (=a set of micro-segments). In both cases, a motion histogram, in which each one of the bins shows the percentage of frames with a specific type of motion and which is defined as indicated by the following relation (5), is used:                                           H            s                    ⁡                      [            i            ]                          =                              N            i                                L            s                                              (        5        )            
where s represents the label of the concerned micro-segment inside the shot, i the motion type (these motions are called trackleft, trackright, boomdown, boomup, tiltdown, tiltup, panleft, panright, rollleft, rollright, zoomin, zoomout, fixed), Ls the length of the micro-segment s, and Ni the number of frames of the micro-segment s with motion type i (it is possible that xcexa3HS[i] greater than 1, since different motions can appear concurrently).
A micro-segment is assumed to be perfectly homogeneous (or to have a very high level of homogeneity) when it presents a single combination of camera motion parameters along all its frames, or to be not homogeneous when it presents important variations on these parameters. The micro-segment homogeneity is computed on its histogram (relation (5)): if a micro-segment is perfectly homogeneous, the histogram bins are equal either to 0 (the considered motion does not appear at all) or to 1 (the motion appears ont he whole segment), while if it is not, the bins can present intermediate values. The measure of the micro-segment homogeneity is then obtained by measuring how much its histogram differs from the ideal one (i.e. it is computed how much the bins of the histogram differ from 1 or 0). The distance corresponding to bins with high values is the difference between the bin value and 1; analogously, for bins with small values, the distance is the bin value itself. An example of histogram is shown in FIG. 3, the axes of which indicate for each motion type its proportion (=motion presence): two motion types introduce some error because the motion does not appear in all the frames of the micro-segment (panleft PL and zoomin ZI), and two other ones (boomdown BD and rollright RR) introduce some error for the opposite reason.
Mathematically, the homogeneity of a micro-segment s is given by the relation (6):                               H          ⁡                      (            s            )                          =                              ∑            i                    ⁢                      e            ⁡                          (              i              )                                                          (        6        )            
where:
e(i)=1xe2x88x92HS[i] if HS[i] 0,5
e(i)=HS[i] if HS[i] less than 0,5
Hs[i]=histogram of the micro-segment s
i=motion type.
The homogeneity of a shot S is then equal to the homogeneity of its micro-segments, weighted by the length of each of them, as illustrated by the following equation (7):                               H          ⁡                      (            S            )                          =                              1                          L              ⁡                              (                S                )                                              ·                                    ∑                              j                =                1                                            j                =                N                                      ⁢                                          L                j                            ·                              H                ⁡                                  (                                      s                    j                                    )                                                                                        (        7        )            
where       L    ⁢          (      S      )        =            ∑      1      N        ⁢          L      j      
is the total length of the shot S and N is the number of micro-segments said shot contains (it may be noted that small values of H(S) correspond to high levels of homogeneity). The distance between two micro-segments s1 and s2 is then the homogeneity of the micro-segments union:
d(s1, s2)=H (s1 U s2)xe2x80x83xe2x80x83(8)
The initial oversegmentation sub-step 121 therefore allows to oversegment the concerned shot in order to obtain a set of perfectly homogeneous micro-segments, which corresponds to the following relation (9):
H(s)=0, whatever s included in Sxe2x80x83xe2x80x83(9)
An example of how to obtain this initial oversegmented partition is shown in FIG. 4, with motion types panleft (PL), zoomout (ZO) and fixed (FIX), s1 to S7 designating the micro-segments (camera motion parameters may be unknown for some frames: in this example, the last frames of the shotxe2x80x94the segment s7xe2x80x94do not have any parameter associated).
The merging sub-step 122 comprises a computation operation, in which the distance between all neighbouring micro-segments (temporally connected) is computed using the equation (8) for selecting the closest pair of micro-segments (for possible merging during the next operation), followed by a fusion decision operation, in which, in order to decide if the selected pair of micro-segments will be merged, the homogeneity of the shot (according to the equation (7)) is computed, assuming that the minimum distance micro-segments have already been merged. The following fusion criterion is applied:
merge if H(S) threshold T(H)
do not merge if H(S) greater than threshold T(H)
(this fusion criterion is global: the decision depends on the homogeneity of the resulting partition, and not exclusively on the homogeneity of the resulting micro-segment). If the merging is done, a new iteration starts at the level of the second sub-step (a second computation operation is carried out, and so on . . . ). The merging process ends when there is no pair of neighbouring micro-segments that can still be merged.
The third step 13 is divided into two sub-steps: a shot merging sub-step 131, in which pairs of shots are grouped together for creating a binary tree, and a tree structuring sub-step 132, for restructuring said binary tree in order to reflect the similarities present in the video sequence.
The shot merging sub-step 131 is provided for yielding a binary tree which represents the merging order of the initial shots: the leaves represent these initial shots, the top node the whole sequence, and the intermediate nodes the sequences that are created by the merging of several shots. The merging criterion is defined by a distance between shots, and the closest shots are first merged. In order to compute the distance between shots, it is necessary to define a shot model providing the features to be compared and to set the neighbourhood links between them (which indicate what merging can be done). The process ends when all the initial shots have been merged into a single node or when the minimum distance between all couples of linked nodes is greater than a specified threshold.
The shot model must obviously allow to compare the content of several shots, in order to decide what shots must be merged and which is their merging order. In still images, luminance and chrominance are the main features of the image, while in a video sequence motion is an importance source of information due to the temporal evolution. So, average images, histograms of luminance and chrominance information (YUV components) and motion information will be used to model the shots.
For implementing the shot merging sub-step 131, it is necessary to carry out the following operations: (a) to get a minimum distance link (operation 1311), (b) to check a distance criterion (operation 1312); (c) to merge nodes (operation 1313); (d) to update links and distances (operation 1314); (e) to check the top node (operation 1315).
In the operation 1311, both the minimum and the maximum distance are computed for every pair of linked nodes. The maximum distance is first checked: if it is higher than a maximum distance threshold d(max), the link is discarded, otherwise the link is taken into account. Once all links have been scanned, the minimum distance is obtained.
In the operation 1312, in order to decide if the nodes pointed by the minimum distance link must be merged, the minimum distance is compared to a minimum distance threshold d(min): if it is higher than said threshold, no merging is performed and the process ends, otherwise pointed nodes are merged and the process goes on.
In the operation 1313, nodes pointed by the minimum distance links are merged. In the operation 1314, said links are updated to take into account the merging that has been done and, once links have been updated, the distance of those links which point to the new mode is recomputed. In the final operation 1315, the number of remaining nodes is checked: if all initial shots have been merged into a single node, the process ends, otherwise a new iteration begins.
The shot merging sub-step 131 may yield a single tree if all the initial shots are similar enough or a forest if initial shots are quite different. An example of binary tree for the creation of a table of contents is shown in FIG. 5. Inside the leaf nodes of this tree, its label and, between brackets, the starting and ending frame numbers of the shot have been indicated; inside the remaining nodes, the label, the fusion order (between parenthesis) and the minimum and maximum distance between its two siblings.
The tree restructuring sub-step 132 is provided for restructuring the binary tree obtained in the sub-step 131 into an arbitrary tree that should reflect more clearly the video structure: the nodes that have been created by the merging process but that do not convey any relevant information are removed, said removal being done according to a criterion based on the variation of the similarity degree (distance) between the shots included in the node:
if the analyzed node is the root node (or one of the root nodes if various binary trees have been obtained after the merging process), then the node should be preserved and appear in the final tree;
if the analyzed node is a leaf node (i.e. corresponds to an initial shot), then it has also to remain in the final tree;
otherwise, the node will be kept in the final tree only if the following conditions (10) and (11) are satisfied:
xe2x80x83|d(min)[analyzed node]xe2x88x92d(min)[parent node]| less than T(H)xe2x80x83xe2x80x83(10)
|d(max)[analyzed node]xe2x88x92d(max)[parent node]| less than T(H)xe2x80x83xe2x80x83(11)
xe2x80x83As shown in FIG. 6, the tree resulting from the restructuring sub-step 132 represents more clearly the structure of the video sequence: nodes in the second level of the hierarchy (28, 12, 13, 21) represent the four scenes of the sequence, while nodes in the third (or occasionally in the fourth) level represent the initial shots.
However, when implementing the method known from the cited document and hereinabove recalled, it may be noticed that this type of method is sometimes sensitive to noise, which then makes difficult to detect peaks of small contrast as those corresponding to fading or special effects.
It is therefore an object of the invention to propose a more robust method for creating the description of a video sequence, in which said limitation is no longer observed.
To this end, the invention relates to a method such as defined in the introductory paragraph of the description and which is moreover characterized in that the shot detection step includes an additional segmentation sub-step, applied to said means displaced frame difference curve and comprising the following operations:
(a) a first filtering operation, based on a structuring element removing the negative peaks the length of which is less than a predefined value (min);
(b) a second filtering operation, based on a contrast filter removing the positive peaks that have a positive contrast lower than a predefined value c;
(c) a marker extraction operation;
(d) a marker propagation operation.